A constraint satisfaction problem (“CSP”) is a mathematical problem that can be solved by satisfying all the constraints of the problem such that the domain of each variable of the problem is narrowed down to a single value without violating any constraint. Each variable has a domain of possible “values,” such as a range of numerical values, an enumerated set of values, a set of items, true/false, etc. Limitations among the variables are expressed as constraints, which act to limit the values that a variable may take.
A constraint solver uses reasoning techniques to find solutions to the CSPs, if any solutions exist. A solution is a state in which the domain of each variable is limited to a single value and no constraint has been violated. A reasoning process includes an “inference” operation, which includes the propagation of the constraints in the attempt to reduce the domain of participating variables, and a “search” operation, which includes making an assignment of a value to each of the variables. By applying reasoning techniques, the constraints are evaluated in order to reduce the domains of the variables. When each domain of the variables is reduced down to a single value without violating any constraints, then a solution to the CSP is found. Thus, a solution to a CSP is a unique assignment of all the variables that satisfies all the constraints of the problem. When a solution is not found, it can be said that the CSP has no solution, or that the CSP is not satisfiable.
“Constraint programming” is a paradigm for solving combinatorial problems using artificial intelligence, computer science, programming languages, operations research, etc. Currently, constraint programming is applied with success to many different technologies, such as scheduling, planning, vehicle routing, configurations, networks, bioinformatics, etc.
An example of a CSP that normally has a unique solution is Sudoku. In a typical Sudoku puzzle, squares are arranged in a 9×9 grid, where each of the 81 squares represents variables. Each variable is usually defined as an integer having a domain ranging from 1 to 9. The typical Sudoku puzzle includes a first constraint that each row in the grid includes all of the integers 1 through 9 without repeating an integer. A second constraint is that each column in the grid includes all the integers 1 through 9 without repeating an integer. A third constraint is that each of nine 3×3 blocks that are arranged in the grid includes all the integers 1 through 9 without repeating an integer. Given the values for several variables throughout the grid, the remaining variables (squares) can be evaluated using various inference techniques, such as a process of elimination, until a solution to the puzzle can be found. In this example, finding the solution to the Sudoku puzzle includes the filling of the squares with the integers 1 through 9 without violating any of the three constraints.
Variables being processed in CSPs can be “floating point variables.” A floating point variable is a variable that includes floating points ranging from a minimum value to a maximum value. A “floating point” refers to a numeric value having a string of digits and a decimal point that “floats” with respect to the string of digits. Regarding the representation of floating point variables in CSPs, the domain of the floating point variable is defined by the minimum and maximum limits, or bounds, of the domain, rather than trying to store all the intermediate values, which would require a very large amount of storage. For example, there are more than 1018 floating point values between a small interval from −1 to 1. FIG. 1 shows an example of the data structure of a conventional domain 10 of a floating point variable. Floating point variable domain 10 contains a minimum bound 12 and a maximum bound 14.